package leetcode.hot100;

import java.util.HashMap;

@SuppressWarnings("all")
public class _146_LRU缓存机制 {

    // 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制

    // 以正整数作为容量 capacity 初始化 LRU 缓存
    public _146_LRU缓存机制(int capacity) {
        // 初始化容量，作为触发内存淘汰机制的触发阈值
        hashMap = new HashMap<>(capacity);
        this.capacity = capacity;
        // 初始化双向链表 head <-> tail
        // 头尾结点都是虚拟结点 dummyNode
        // 这样设置虽然多占用了两个没有用的结点空间，但是极大的方便了插入和删除操作
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.perv = head;
    }

    // 在 O(1) 时间复杂度内完成下面这两种操作
    // 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
    public int get(int key) {
        Node node = hashMap.get(key);
        if (node == null) return -1;
        // 将被访问过的结点移动到首部
        removeNode(node);
        addToHead(node);
        return node.val;
    }

    // 如果关键字已经存在，则变更其数据值；
    // 如果关键字不存在，则插入该组「关键字-值」
    // 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间
    public void put(int key, int value) {
        Node node = hashMap.get(key);
        // 存在，更新并移动
        if (node != null) {
            node.val = value;
            removeNode(node);
            addToHead(node);
            return;
        }
        // 触发内存淘汰策略
        // 先删除链表尾部结点---再添加新结点
        if (hashMap.size() == capacity) {
            // 注意：还有删除哈希表中的数据
            hashMap.remove(clearMemory().key);
        }
        // 不存在，新建
        node = new Node(key, value);
        hashMap.put(key, node);
        // 在没有触发淘汰策略的前提下直接往首部添加即可
        addToHead(node);
    }

    // 通过key定位到Node结点，实现对链表结点的O(1)时间复杂度查找
    private final HashMap<Integer, Node> hashMap;

    // 构建双向链表
    private final Node head;
    private final Node tail;
    // 内存容量
    private final int capacity;

    // 定义结点内部结构
    private static class Node {
        Node next;
        Node perv;
        int key;
        int val;

        public Node(int val) {
            this.val = val;
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 将结点插入链表头部
    private void addToHead(Node node) {
        Node next = head.next;
        head.next = node;
        node.perv = head;
        node.next = next;
        next.perv = node;
    }

    // 删除结点
    private void removeNode(Node node) {
        node.perv.next = node.next;
        node.next.perv = node.perv;
    }

    // 淘汰最后一个结点
    private Node clearMemory() {
        Node perv = tail.perv;
        perv.perv.next = tail;
        tail.perv = perv.perv;
        return perv;
    }

}
